The Viterbi algorithm is commonly used for decoding convolution-encoded signals in the field of data communications, data recording, digital signal processing, and etc. For example, in a communication system, data symbols transmitted from a transmitter can be convolution-encoded to improve transmission reliability. During transmission, the signal likely has noise and intersymbol interference (ISI) introduced by channel distortion. Correspondingly, an error-correction decoding process is performed at the receiver to decode the convolution-encoded data symbols, and cancel the intersymbol interference (ISI).
A decoding process involves comparing a received data sequence continuously with theoretically possible transmission data sequences. The level of match is used, as the basis for a decision according to Maximum Likelihood Sequence Estimation (MLSE). More specifically, a trellis diagram is used to describe the coding rules. A Viterbi decoder in the receiver calculates the metrics to determine an optimum path in the trellis diagram that has the best path metric, for example the highest or the lowest path metric depending on the configuration of the Viterbi decoder. The Viterbi decoder uses this selected optimum path to determine the decoded data sequence, and then passes it to a data sink.
According to the Viterbi algorithm, each path metric of a path leading to a specific state is composed of the path metric of a previous state in time and of the branch metric of the branch leading from this previous state to the specific state. The path that has the best path metric up to this time is determined for each state, referred to as a “survival path.” During each time step, there are a number of such survivor paths corresponding to the number of different states. Thus, the path metric depends on the path metrics of the previous time step connected to the state via one branch.
Typically a Viterbi decoder includes a branch metric circuit for calculating branch metrics, a path metric circuit for calculating path metrics as a function of the branch metrics, and an Add-Compare-Select (ACS) unit for selecting the optimum path metric from a set of path metrics. FIG. 1 illustrates the configuration of a compare-select circuit 100 in an ACS unit according to the prior art. The ACS unit includes adders (not shown) for calculating path metrics (or state metric values) x1-x4, comparators 101-103 for comparing the path metrics x1-x4 and multiplexers 111-113 for outputting the minimum of x1-x4 based on the comparison results.
More specifically, the first level comparators 101 and 102 compare the state metric values x1-x4 in distinct pairs and output decision signals s1 and s2, each decision signal indicating the smaller value of the corresponding pair. The decisions signals s1 and s2 are directly used as the select control signals for the first level multiplexers 111 and 112. Accordingly, each first level multiplexer 111 or 112 outputs the smaller path metric u1 or u2 of the corresponding pair (x1,x2) or (x3,x4). u1 or u2 are then compared at the second level comparator 103, which produces a decision signal s3 used for controlling the second level multiplexer 113 to output the smaller of u1 and u2, or min(x1, x2, x3, x4).
According this configuration, to output the minimum of the 4 state metrics x1-x4, the first level comparators 101-102, the first level multiplexers 111-112, the second level comparators 103 and the third level multiplexer 113 have to operate in sequence. The sequential nature of this compare-select algorithm contributes to undesirably long latency in an ACS unit. In generally, an ACS unit is the most computationally intensive part of a Viterbi decoder and regarded as the main bottleneck on the decoding speed. Further, such an ACS unit also occupies the greatest chip area and consumes the most power in the decoder. As can be seen from FIG. 1, the complexity of an ACS unit can increase exponentially with the complexity of the respective code used for channel coding.